package baseclass.m_graph;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 并查集
 * @date 2020/3/6 21:44
 */
public class UnionFindSet {
    //K是当前节点，V是当前并查集的代表节点
    private Map<Node,Node> fatherMap;
    //K是当前节点，V是当前并查集大小
    private Map<Node,Integer> mapSize;

    public UnionFindSet(List<Node> nodes) {
        fatherMap = new HashMap<>();
        mapSize = new HashMap<>();
        for (Node node : nodes) {
            fatherMap.put(node,node);
            mapSize.put(node,1);
        }
    }
    //查找当前节点所属的并查集的代表节点
    //做了优化，当前节点到代表节点的所有节点都直接指向代表节点
    private Node findFather(Node node){
        //所有节点的father一样，节点一个一个往上滑
        Node father = fatherMap.get(node);
        //说明还没有找到
        if(father != node) {
            //递归去找，findHead(father)最后每层都是father节点
            father = findFather(father);
        }
        //当前节点指向 代表节点
        fatherMap.put(node,father);
        return father;
    }
    public boolean isSameSet(Node a, Node b) {
        return findFather(a) == findFather(b);
    }
    public void union(Node a,Node b){
        if(a == null || b == null)
            return;
        Node ahead = findFather(a);
        Node bhead = findFather(b);
        if(ahead != bhead){
            //判断谁长
            int asize = mapSize.get(a);
            int bsize = mapSize.get(b);
            if(asize <= bsize){
                //把a挂在b下面
                fatherMap.put(ahead,bhead);
                mapSize.put(bhead,asize + bsize);
            }else{
                fatherMap.put(bhead,ahead);
                mapSize.put(ahead,asize + bsize);
            }
        }
    }

}
